1. Field of the Invention
The present invention relates to a method for memory space management. In particular, the present invention uses a resident program to monitor the memory space and the file system allocation to release the memory space that has been occupied by invalid data.
2. Description of Related Art
The application system of a computer usually uses the file system to access the storage device. The addressing method of the file system is a logical block address (LBA) that uses the sector with a capacity of 512 bytes as a unit. When the storage device records a data, a physical block address that can clearly and accurately address the location of the data is used to address the allocation, such as address location within a device, a memory block, or a memory page, etc. The logical-to-physical address translation is meant to perform a translation between the logical address that is accessed by the application system and the physical address that stores data.
The relation between the logical address and the physical address is shown in FIG. 1. The address for the logical address 11 is from 0 to 2047999. In this example, each address corresponds to a memory capacity with 512 bytes. The memory is divided into a plurality of segments, including segment 0 to segment 31. The logical address 0 to 63999 forms a segment (i.e. segment 0). In the figure, the relation between the logical block address (LBA) 12 and the physical block address (PBA) 14 is mapped by a logical-to-physical mapping table (L2P mapping table) 13.
Each segment is divided into 256 logical block addresses 12, wherein 6 out of the 256 logical block addresses 12 are reserved as the spare blocks (or so called free blocks). In physical block addresses 14, 250 out of 256 physical blocks (i.e. 6 logical block address are reserved therefore 6 logical blocks are reserved, which leaves 250 physical blocks) correspond to 250 logical blocks. Therein 6 physical block addresses 14 are reserved as the spare blocks (or so called free blocks) for recording the control data, such as storing the logical-to-physical mapping table 13, replacing the bad block, or storing the updated data when data is updated. When data is updated and stored to a new block, the original physical block which stores data is erased and released to be the spare block.
For the logical address 11, there are 32 segments (segment 0˜31). Each segment includes 250 logical blocks (i.e. 256 logical block address 12 with 6 logical block address reserved therefore there are 250 logical blocks). Each logical block corresponds to a physical block via the logical-to-physical mapping table 13, and can store 128 KB data. For meeting the capacity of the memory page of the physical block, the logical block is divided into 64 continuous memory pages. Each memory page is 2 KB and includes 4 continuous sectors, it means that each logical block includes 256 continuous sectors.
For the physical address, each segment includes 256 physical blocks, and each physical block includes 64 memory pages that can store 128 KB data and is mapped to a logical block via the logical-to-physical mapping table 13. The physical block (i.e. should have 6 free blocks) that is not mapped to the logical block can be the spare block, a bad block (not shown in the figure) due to the physical block is bad, or a boot block.
In the mapping relation between the logical address space and the physical address shown in FIG. 1, each address of the logical addresses 11 represents a sector that can store 512 bytes data. The logical address 11 is divided by the capacity of the block unit (the capacity of each of the logical block (128K) is equal to 256 sectors, this means 128 KB user data). The quotient is the logical block address 12. The remainder is divided by the capacity of the memory page unit to represent the quantity of the sectors. For example, the capacity of the memory page unit (2 KB) represents 4 continuous sectors so that the logical page address can be calculated. The logical address (100/256=0 with reminder of 100) corresponds to the logical block address 0, and corresponds to the memory page address 25 (100/4=25). The logical address (256/256=1 with reminder of 0) corresponds to the logical block address 1, and corresponds to the memory page address 0.
Therefore, after the application system obtains the logical block address 12 via the file system, the application searches the logical-to-physical mapping table 13 to find out the corresponding physical block address 14. In the prior art, in order to reduce the space for storing the logical-to-physical mapping table 13, the logical-to-physical mapping table 13 is divided into a plurality of segments. Each segment is mapped by a logical-to-physical mapping table 13. The mapping relation between a continuous logical addressing space and a continuous physical addressing space for each segment is recorded by an independent logical-to-physical mapping table. For example, segment 0 stores the logical address 0˜63999, and the mapping relation between the logical block addresses 0˜249 (250 logical blocks that is equal to the 32 MB user data and the physical block addresses 0˜255 (256 physical memory blocks, with 6 unmatched free blocks). Similarly, segment 31 stores the logical addresses 1984000˜2047999, and the mapping relation between the logical block addresses 7750˜7999 (250 logical blocks that is equal to the 32 MB user data and the physical block addresses 7936˜8191 (256 physical memory blocks, with 6 unmatched free blocks).
Because the mapping relation between the logical block address and the physical block address is continuous, the segment number for storing the logical block can be easily obtained by dividing the logical block address by the quantity of the logical blocks of a single segment. Next, the logical-to-physical mapping table 13 for the segment is loaded and searched to find out the physical block address 14 for storing the user data of the logical block.
However, the file system for the application system usually is designed for a magnetic storage medium (such as a hard disk). For example, the file systems for Microsoft operation system (FAT16, FAT32, NTFS, etc) or Mac OS (HFS, HFS+, etc) directly erase the allocation in the allocation table or the allocation bit-map when a file is erased. For example, for the FAT file system, the file erasing operation is merely implemented by erasing the file name in the root direction or the sub direction, and recovering the cluster chain occupied by the file to zero.
The above operation for the storage device of the prior art is to perform a writing operation for updating data to the logical address. It cannot obtain the status of the data stored on the physical address (i.e. valid or invalid). It also has the same drawbacks for the flash memory. Furthermore, when an updating operation or an erasing operation is executed, the access speed is affected and the usage life of the storage medium is reduced due to the physical block is occupied by the invalid data and the invalid data is moved.